package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description: 24. 两两交换链表中的节点  递归
 * @date: 2020/11/13 17:21
 */
public class J0024_M_SwapPairs {

    public static ListNode swapPairs(ListNode head) {
        //终止条件 没有节点或就一个节点
        if (head == null || head.next == null) {
            return head;
        }
        //把下一个节点当作头结点取出来 并指向原来的头节点
        ListNode next = head.next;
        //先把后面的节点(第三个)交换好，然后用原来的head节点指向它
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

    /**
     * 暴力迭代试试
     * 1 - 2 - 3 -4 -5 - 6
     *  先交换1-2
     */
    public static ListNode swapPairs2(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = dummy;
        //交换当前节点的后两个 cur  next nnext  cur.nexct->nnexct   nnexct.next->next   next.next->nnext.next
        while (cur.next != null && cur.next.next != null) {
            ListNode next = cur.next;
            ListNode nnext = cur.next.next;
            //先把当前节点指向nnext
            cur.next = nnext;
            next.next = nnext.next;
            // 再把nnext指向原来的next节点
            nnext.next = next;
            //把当前节往后移动2位
            cur = nnext;
        }
        return dummy.next;
    }


    public static void main(String[] args) {
        ListNode node = new ListNode(new int[]{1, 2, 3, 4, 5, 6});
        System.out.println(node);
        System.out.println(swapPairs2(node));
    }
}
